package 二零年3月;
/*
* 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，
* 编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
    示例2:
 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

思路：使用动态规划解决问题，这道题属于背包问题，往背包里面加新的种类并判断

核心思想是：dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]

思路：1：令dp[i][j]为遍历到当下这个硬币时，组成的金额j的数目
      2：这有两种情况：（1）当前这个硬币没有取，dp[i][j]=dp[i-1][j]   //当前这种硬币没有取时背包里面的符合条件的数目
                        (2)当前这个硬币取了， dp[i][j]=dp[i][j-coins[i]] //取了这种硬币时，背包里面新产生的数目

         将这两种情况相加的和就是返回的结果
* */
public class InterView0811 {
    public int waysToChange(int n) {
        if(n<5){
            return 1;
        }
        if(n==5){
            return 2;
        }
        //dp[i][j]:表示第i种硬币加入时硬币总值为j的数目
        int[][] dp=new int[4][n+1];
        int [] coins={1,5,10,25};  //这四种硬币的额度

        //当背包里面只有一种硬币时，只有一种表示方法
        for (int i=0;i<=n;i++){
            dp[0][i]=1;
        }
        //当数量为0时，有一种表示方法
        for(int i = 0; i < 4; i++){
            dp[i][0] = 1;
        }
        /*
         * 状态：dp[i][j]表示[0...i]种硬币能组合为j的所有不同种数
         * 状态转移：取 或 不取 当前硬币coins[i]
         *
          因为这是往背包里面加硬币种类，所以从i=1开始,具体逻辑看上面的解释
         */
        for (int i = 1; i <4 ; i++) {
            for (int j =1; j <=n ; j++) {
                if(j>=coins[i]){
                    dp[i][j]=(dp[i-1][j]+dp[i][j-coins[i]])%1000000007;
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[3][n];
    }
}
